#include <string>  // string

using namespace std;

class Solution {
   public:
    string addBinary(string a, string b) {
        string ans = "";
        int i = 0;      // 当前位
        int carry = 0;  // 进位
        while (i < a.size() || i < b.size() || carry) {
            int now = carry;
            if (i < a.size() && a[a.size() - i - 1] == '1') ++now;
            if (i < b.size() && b[b.size() - i - 1] == '1') ++now;
            ans += (now == 0 || now == 2) ? '0' : '1';
            carry = (now == 2 || now == 3) ? 1 : 0;
            i += 1;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};